package com.lft.queue03.priority_queue;

/**
 * 优先级队列
 */
public class PriorityQueueDemo {
	public static void main(String[] args) {
		Letter l1 = new Letter("张三", 10);
		Letter l2 = new Letter("李四", 1);
		Letter l3 = new Letter("王五", 11);
		Letter l4 = new Letter("杰克", 5);
		Letter l5 = new Letter("汤姆", 3);
		Letter l6 = new Letter("约翰", 7);
		
		PriorityQueue pq = new PriorityQueue(10);
		
		pq.insert(l1);
		pq.insert(l2);
		pq.insert(l3);
		pq.insert(l4);
		pq.insert(l5);
		pq.insert(l6);
		
		// 遍历
		pq.list();
		System.out.println("===================");
		
		// 查看头和尾
		System.out.println("队列头元素是：" + pq.peekFront());
		System.out.println("队列尾元素是：" + pq.peekRear());
		System.out.println("===================");
		
		// 操作删除
		System.out.println(pq.remove());
		
		System.out.println("===================");
		
		// 遍历
		pq.list();
		
	}
}

class PriorityQueue {
	/**
	 * 数组模拟队列
	 */
	private Letter[] letters;
	/**
	 * 数量
	 */
	private int count;
	/**
	 * 容量
	 */
	private int maxSize;
	/**
	 * 头
	 */
	private int front;
	/**
	 * 尾
	 */
	private int rear;
	
	/**
	 * 构造器，传入队列的容量大小，初始化一个队列。
	 * @param maxSize 队列的容量大小。
	 */
	public PriorityQueue(int maxSize) {
		this.maxSize = maxSize;
		letters = new Letter[maxSize];
		front = 0;
		rear = -1;
		count = 0;
	}
	
	/**
	 * 判断队列是否已满
	 * @return boolean
	 */
	public boolean isFull() {
		return count == maxSize;
	}
	
	/**
	 * 判断队列是否为空
	 * @return boolean
	 */
	public boolean isEmpty() {
		return count == 0;
	}
	
	/**
	 * 返回队列中元素的个数
	 * @return int
	 */
	public int size() {
		return count;
	}
	
	public void insert(Letter letter) {
		// 队列满
		if (isFull()) {
			System.out.println("队列已满，无法添加！！");
			return;
		}
		// 队列中没有元素
		if (count == 0) {
			letters[++rear] = letter;
		}
		// 队列中有元素
		else {
			int i = 0;
			// 从后往前遍历
			for (i = count - 1; i >= 0; i--) {
				// 要插入的元素的优先级大于当前元素的优先级。
				if (letter.getPriorty() > letters[i].getPriorty()) {
					// 把当前元素往后移。
					letters[i + 1] = letters[i];
				} else {
					//  否则就跳出循环
					break;
				}
			}
			// 插入在当前位置
			letters[i + 1] = letter;
			rear++;
		}
		count++;
	}
	
	/**
	 * 删除队列中的一个元素。
	 * @return 被删除的元素。
	 */
	public Letter remove() {
		if (isEmpty()) {
			System.out.println("队列为空，无法删除！");
			return null;
		}
		count--;
		return letters[front++];
	}
	
	/**
	 * 看一下队列中的头元素是哪个。
	 * @return 头元素。
	 */
	public Letter peekFront() {
		return letters[front];
	}
	
	/**
	 * 看一下队列中的尾元素是哪个。
	 * @return 尾元素。
	 */
	public Letter peekRear() {
		return letters[rear];
	}
	
	/**
	 * 遍历
	 */
	public void list() {
		int temp = front;
		for (int i = temp; i <= rear; i++) {
			System.out.println(letters[i]);
		}
	}
	
}

/**
 * 书信类
 */
class Letter {
	private String fromName;
	private int priorty;
	
	public Letter(String fromName, int priorty) {
		this.fromName = fromName;
		this.priorty = priorty;
	}
	
	public String getFromName() {
		return fromName;
	}
	
	public void setFromName(String fromName) {
		this.fromName = fromName;
	}
	
	public int getPriorty() {
		return priorty;
	}
	
	public void setPriorty(int priorty) {
		this.priorty = priorty;
	}
	
	@Override
	public String toString() {
		return "Letter [" +
				"fromName='" + fromName + '\'' +
				", priorty=" + priorty +
				']';
	}
}